package leetcode.stackandqueue;

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands200 {
    //dfs
    class Solution1 {
        int[] help = {-1, 0, 1, 0, -1};
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int num = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        dfs(grid, i, j);
                        ++num;
                    }
                }
            }
            return num;
        }

        public void dfs(char[][] grid, int i, int j) {
            if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
                return;
            }
            grid[i][j] = '0';
            for (int k = 0; k < 4; k++) {
                dfs(grid, i + help[k], j + help[k + 1]);
            }
        }
    }

    //bfs
    class Solution2 {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid == null || grid[0].length == 0) {
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int ans = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        ++ans;
                        bfs(i, j, grid);
                    }
                }
            }
            return ans;
        }

        int[] help = {-1, 0, 1, 0, -1};
        public void bfs(int i, int j, char[][] grid) {
            int[] xy = new int[]{i, j};
            Queue<int[]> queue = new LinkedList<>();
            queue.add(xy);
            while (!queue.isEmpty()) {
                int[] curXY = queue.poll();
                grid[curXY[0]][curXY[1]] = '0';
                for (int k = 0; k < 4; k++) {
                    int r = curXY[0] + help[k];
                    int c = curXY[1] + help[k + 1];
                    if (r >= 0 && c >= 0 && r < grid.length && c < grid[0].length && grid[r][c] == '1') {
                        grid[r][c] = '0';
                        queue.add(new int[]{r, c});
                    }
                }
            }
        }
    }


    //FIXME:有问题
    class Solution3 {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int ans = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        ans++;
                        bfs(i, j, grid);
                    }
                }
            }
            return ans;
        }



        int[] help = {-1, 0, 1, 0, -1};
        public void bfs(int i, int j, char[][] grid) {
            Queue<Integer> queue = new LinkedList<>();
            int m = grid.length;
            int code = i * m + j;
            queue.add(code);
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                int x = poll / m;
                int y = poll % m;
                grid[x][y] = '0';
                for (int k = 0; k < 4; k++) {
                    int r = x + help[k];
                    int c = y + help[k + 1];
                    if (r >= 0 && c >= 0 && r < grid.length && c < grid[0].length && grid[x][y] == '1') {
                        grid[x][y] = '0';
                        queue.add(x * m + y);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        new NumberOfIslands200().new Solution3().numIslands(new char[][] {
                {'1', '1', '0' ,'0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        });
    }
}


